你的任務 🎯
給定 $N$ 個行星的二維座標，以最低成本重建「超空間航道」網絡，使所有行星重新連接。
- 目標： 將全部 $N$ 個行星（頂點）連結起來，確保彼此皆可到達（直接或間接）。
- 目的： 找出能將總成本降至最低的網路設計。
分析 🛰️
航道（邊）的成本為歐幾里得距離：
$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
- 任何兩顆行星之間都可以建造一條航道，任意兩顆行星之間。
- 這表示我們構成了一個完全（稠密）圖。
解法 ⚙️
這是一個典型的最小生成樹（MST）問題。
- 演算法： 提示建議使用普里姆演算法（Prim's Algorithm）（$O(V^2)$ 版本），非常適合處理稠密圖。
- 起始點： 我們將從行星 0 開始演算，以確保結果一致。
一個完全圖（左側）包含所有可能的邊；最小生成樹（右側）是連接所有頂點且成本最低的邊集。